%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2013 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{algorithmic}[1]
%% input and output
\Require A digraph $G = (V, E)$ that has no self-loops. Vertices are
  numbered from $1$ to $n$, i.e.~$V = \{1, 2, \dots, n\}$.
\Ensure The boolean matrix $T$ such that $T[i,j] = 1$ if and only if
  there is an $i$-$j$ path in $G$, and $T[i,j] = 0$ otherwise.
%%
%% algorithm body
\State $n \gets |V|$
\State $T \gets$ adjacency matrix of $G$
%% \For{$i \gets 1, 2, \dots, n$}{
%%   \For{$j \gets 1, 2, \dots, n$}{
%%     \eIf{$i = j$ \emph{or} $ij \in E$}{
%%       $T[i,j] \gets 1$
%%     }{
%%       $T[i,j] \gets 0$
%%     }
%%   }
%% }
\For{$k \gets 1, 2, \dots, n$}
  \For{$i \gets 1, 2, \dots, n$}
    \For{$j \gets 1, 2, \dots, n$}
      \State $T[i,j] \gets T[i,j] \vee \big( T[i,k] \wedge T[k,j] \big)$
    \EndFor
  \EndFor
\EndFor
\State \Return $T$
\end{algorithmic}
